#pragma once
#include<iostream>
#include<vector>
using namespace std;

int Hirshberg(vector<int>& first_string, vector<int>& second_string)
{
	int first_length = first_string.size();
	int second_length = second_string.size();

	vector<vector<int> >dinamic_mistakes(first_length + 1, vector<int>(second_length + 1, 0));

	for(int column = 0; column<=first_length; ++column)dinamic_mistakes[column][0] = column;
	for(int row = 0; row<=second_length; ++row)dinamic_mistakes[0][row] = row;

	for(int column = 1; column<=first_length; ++column)
		for(int row = 1; row <= second_length; ++row)
		{
			dinamic_mistakes[column][row] = min(dinamic_mistakes[column][row - 1] + 1, dinamic_mistakes[column - 1][row] + 1);
			if (first_string[column - 1] == second_string[row - 1]) 
				dinamic_mistakes[column][row] = min (dinamic_mistakes[column][row], dinamic_mistakes[column - 1][row - 1]);
		}

		/*cout << "checkin\n";

		for(int i = 1; i<=first_length; ++i, cout << "\n")
			for(int j = 1; j<=second_length; ++j)
				cout << dinamic_mistakes[i][j] << " ";
		cout << "\n";*/
		return dinamic_mistakes[first_length][second_length];
	
}

vector<vector<int> > Shortest_Path(vector<int>& first_string, vector<int>& second_string)
{
	int first_length = first_string.size();
	int second_length = second_string.size();

	vector<vector<int> >dinamic_mistakes(first_length + 1, vector<int>(second_length + 1, 0));

	for(int column = 0; column<=first_length; ++column)dinamic_mistakes[column][0] = column;
	for(int row = 0; row<=second_length; ++row)dinamic_mistakes[0][row] = row;

	for(int column = 1; column<=first_length; ++column)
		for(int row = 1; row <= second_length; ++row)
		{
			dinamic_mistakes[column][  row] = min(dinamic_mistakes[column][row - 1] + 1, dinamic_mistakes[column - 1][row] + 1);
			if (first_string[column - 1] == second_string[row - 1]) 
				dinamic_mistakes[column][row] = min (dinamic_mistakes[column][row], dinamic_mistakes[column - 1][row - 1]);
		}

		/*cout << "checkin\n";

		for(int i = 1; i<=first_length; ++i, cout << "\n")
			for(int j = 1; j<=second_length; ++j)
				cout << dinamic_mistakes[i][j] << " ";
		cout << "\n";*/
		return dinamic_mistakes;
	
}

vector<vector<int> > Shortest_Path_For_Reversed(vector<int>& first_string, vector<int>& second_string)
{
	int first_length = first_string.size();
	int second_length = second_string.size();

	vector<vector<int> >dinamic_mistakes(first_length + 1, vector<int>(second_length + 1, 0));

	for(int column = 0; column<=first_length; ++column)dinamic_mistakes[column][second_length] = first_length - column;
	for(int row = 0; row<=second_length; ++row)dinamic_mistakes[first_length][row] = second_length - row;

	for(int column = first_length - 1; column >= 0; --column)
		for(int row = second_length - 1; row >= 0; --row)
		{
			dinamic_mistakes[column][row] = min(dinamic_mistakes[column][row + 1] + 1, dinamic_mistakes[column + 1][row] + 1);
			if (first_string[column] == second_string[row]) 
				dinamic_mistakes[column][row] = min (dinamic_mistakes[column][row], dinamic_mistakes[column + 1][row + 1]);
		}

		/*cout << "checkin\n";

		for(int i = 1; i<=first_length; ++i, cout << "\n")
			for(int j = 1; j<=second_length; ++j)
				cout << dinamic_mistakes[i][j] << " ";
		cout << "\n";*/
		return dinamic_mistakes;
	
}

 bool check_way(vector<int>& first_string, vector<int>& second_string, int mistakes, vector<pair<int, int> >& path)
 {
	 int cost = 0;
	 int coor_X = path[0].first;
	 int coor_Y = path[0].second;
	 if (coor_X != 0 || coor_Y != 0){cout << "wrong_first_point\n";return false;}
	 for(int point = 1; point < path.size(); ++point)
	 {
		int next_coor_X = path[point].first;
		int next_coor_Y = path[point].second;
		if (next_coor_X == coor_X + 1 && next_coor_Y == coor_Y)++cost; else
		if (next_coor_Y == coor_Y + 1 && next_coor_X == coor_X)++cost; else
			if (next_coor_X == coor_X + 1 && next_coor_Y == coor_Y + 1){if (first_string[coor_X] != second_string[coor_Y]){cout << "wrong_diag\n"; return false;}}else
			{cout << "wrong_rotate\n";return false;}
		coor_X = next_coor_X;
		coor_Y = next_coor_Y;
	 }
	 if (cost != mistakes) {cout << "wrong_cost\n" << mistakes << " " << cost << "\n";return false;} 
	 return true;
 }